package oj;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class LC354 {
    class Solution {
        public int maxEnvelopes(int[][] envelopes) {
            if (envelopes.length == 0) return 0;
            Arrays.sort(envelopes,new Comparator<int[]>(){
                public int compare(int[] a,int[] b){
                    return a[0]==b[0]?b[1]-a[1]:a[0]-b[0];
                }
            });
            List<Integer> list=new ArrayList<>();
            list.add(envelopes[0][1]);
            for(int i=1;i<envelopes.length;i++){
                int num=envelopes[i][1];
                if(num>list.get(list.size()-1)){
                    list.add(num);
                }else{
                    int index=binarySearch(list,num);
                    list.set(index,num);
                }
            }
            return list.size();
        }

        private int binarySearch(List<Integer> list,int target){
            int low=0;
            int high=list.size()-1;
            while(low<high){
                int mid=(high-low)/2+low;
                if(list.get(mid)<target){
                    low=mid+1;
                }else{
                    high=mid;
                }
            }
            return low;
        }
    }

}
